package com.ccsoft.leetcode.service;

import ch.qos.logback.core.joran.conditional.ElseAction;
import org.springframework.stereotype.Service;

import java.util.*;

/**
 * 2021年11月10日 08:12:21 chanchaw
 * 在做 leetcode 69. Sqrt -  自定义算数平方根算法时了解到该算法 - 逆波兰表达式 - 逆波兰表示法
 * 用于制作计算器程序，本案例实现逆波兰表达式的制作，顺手实现计算器算法
 */
@Service
public class ReversePolishNotation {
    private static final String LEFT_BRACKET = "(";
    private static final String RIGHT_BRACKET = ")";

    /**
     * 传入一个计算表达式，返回逆波兰表示法的栈结构对象
     * @param expression
     * @return
     */
    public String getReversePolishNotation(String expression){
        Deque<String> stack = getPolishStack(expression);

        String ret = "";
        while(stack.size() != 0){
            ret = ret + stack.poll();
        }
        return ret;
    }

    public LinkedList<String> getPolishStack(String expression){
        LinkedList<String> s1 = new LinkedList<>();// 操作符栈
        LinkedList<String> s2 = new LinkedList<>();// 数字栈

        for(int i=0;i<expression.length();i++){
            String one = expression.substring(i,i+1);// 单个字符
            if(!isOperator(one))
                s2.push(one);// 将操作数压入 s2
            else
                resolveOperator(s1,s2,one);
        }

        // 将 s1 中剩余的所有元素压入 s2 ，并依次弹出构建 逆波兰表达式
        while(s1.size() != 0){
            s2.push(s1.poll());
        }

        return s2;
    }

    /**
     * 2021年11月10日 08:36:14 chanchaw
     * 前提条件：s1 - 保存运算符的栈
     *          s2 - 保存操作数的栈 - 会同时保留运算符
     * 从左向右处理表达式时当遇到操作符则调用本方法，处理逻辑：
     * 1. 如果 s1 是空，或者栈顶是左括号则将 ope 压入 s1
     * 2. 如果 ope 优先级高于栈顶元素，则压入 s1
     * （乘除先与加减，括号优先级最低，即：乘除优先级=1，加减优先级=0，括号优先级=-1）
     * 3. 其他情况弹出 s1 栈顶元素压入 s2，继续对比栈顶元素 - 回到步骤1重新开始
     *     如果遇到同级别优先级的运算符，则将现有栈顶元素运算符压入 s2，然后循环判断栈顶元素
     *     直至找到非同级别优先级的运算符 - 即找到优先级别更小的运算符为止 - 或者运算符栈 s1 为空
     * 4. 如果是右括号则依次弹出 s1 的栈顶元素压入到 s2 直到遇到左括号。注意括号最终是抛弃的
     *      即不管 s1,s2 最终都不会有括号
     * 案例：1+((2+3)*4)-5
     * 的逆波兰表达式是：1 2 3 + 4 * + 5 -
     * 每一步的执行步骤见图片：src/main/resources/static/逆波兰表达式执行步骤.jpg
     *
     * 此处没有返回被操作的两个栈对象 s1,s2。要理解 java 方法传参的副本逻辑，不像 c++ 中的引用
     * @param s1
     * @param operator
     * @return
     */
    private void resolveOperator(LinkedList<String> s1,LinkedList<String> s2,String operator){
        if( s1.size()<=0 ){
            s1.push(operator);
        }else if (LEFT_BRACKET.equals(operator)) {
            s1.push(operator);
        }else if(RIGHT_BRACKET.equals(operator)) {
            while(s1.size()>0){
                String lastOne = s1.poll();
                if( LEFT_BRACKET.equals(lastOne) )
                    break;// 遇到闭合的左括号则跳出循环执行传入表达式的右边的新字符
                else
                    s2.push(lastOne);// 不是闭合的左括号则压入s2
            }
        }else if(priority(operator,s1.getFirst()) >0 ){
            s1.push(operator);
        }else{
            s2.push(s1.poll());
            resolveOperator(s1,s2,operator);
        }
    }

    /**
     * 2021年11月10日 08:18:55 chanchaw
     * 返回运算符构成的数组
     * @return
     */
    public String[] getOperators(){
        return new String[]{"+","-","*","/"};
    }

    /**
     * 返回带有优先级别的操作符构成的 Map 对象
     * @return
     */
    private Map<String,Integer> getOperatorWithPriority(){
        Map<String,Integer> ret = new HashMap<>();
        ret.put("+",0);
        ret.put("-",0);
        ret.put("*",1);
        ret.put("/",1);
        ret.put("(",-1);
        return ret;
    }

    /**
     * 传入一个字符判断是否是运算符
     * @param one 被判断的字符
     * @return 是运算符则返回 true，相反则返回 false
     */
    public boolean isOperator(String one){
        String[] operators = getOperators();
        for(int i=0;i<operators.length;i++){
            if( one.equals(operators[i]) ) return true;
        }

        if(LEFT_BRACKET.equals(one) || RIGHT_BRACKET.equals(one)) return true;
        return false;
    }

    /**
     * 判断两个操作符的优先级，前者优先则返回1
     * 二者相等则返回0，前者优先级低则返回-1
     * @param ope1
     * @param ope2
     * @return 前面操作符优先级别高则返回1，相同则返回0，低则返回-1
     */
    private int priority(String ope1,String ope2){
        Map<String,Integer> operators = getOperatorWithPriority();
        Integer priority1 = operators.get(ope1);
        Integer priority2 = operators.get(ope2);
        return priority1 - priority2;
    }

    public void test1(){
        Deque<String> s1 = new LinkedList<>();
        s1.push("a");
        s1.push("b");
        test2(s1);
        System.out.println("父方法中栈结构数据是：" + s1.toString());
    }

    public void test2(Deque s){
        System.out.println("操作方法追加数据前：" + s.toString());
        s.push("c");
        System.out.println("操作方法追加数据后：" + s.toString());
    }
}
